package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class MergeIntervals {

    public static void main(String[] args) {
        MergeIntervals mergeIntervals = new MergeIntervals();
//        int[][] in = new int[][]{new int []{1,4}, new int[]{4,5}};
//        [[1,3],[2,6],[8,10],[15,18]]
        int[][] in = new int[][]{new int []{1,3}, new int[]{2, 6}, new int[]{8, 10}, new int[]{15, 18}};
        int[][] merge = mergeIntervals.merge(in);
        for (int i = 0; i < merge.length; i++) {
            for (int i1 = 0; i1 < merge[i].length; i1++) {
                System.out.print(merge[i][i1] + " ");
            }
            System.out.println();
        }
    }

    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(i -> i[0]));
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            int L = intervals[i][0], R = intervals[i][1];
            if(list.size() == 0 || list.get(list.size() - 1)[1] < L){
                list.add(new int[]{L, R});
            }else{
                int[] arr = list.get(list.size() - 1);
                arr[1] = Math.max(arr[1], R);
                list.set(list.size() - 1, arr);
            }
        }
        return list.toArray(new int[][]{});
    }


}
